Agenci

Limit pamięci: 32 MB

W kraju działają agenci obcych wywiadów. Zajmują się oni nie tylko wykradaniem tajemnic, ale także nawzajem się szpiegują. Mówimy, że agent rozpracował agenta , jeśli posiada dokumenty wystarczające do aresztowania .

Niektórzy agenci są przekupni — w zamian za odpowiednią sumę pieniędzy są gotowi oddać wszystkie posiadane dokumenty. Aresztując agenta przechwytujemy wszystkie zgromadzone przez niego dokumenty. Przekupienie odpowiednio wybranych agentów może więc uruchomić łańcuch aresztowań prowadzący do zlikwidowania wszystkich agentów działających w kraju.

Rodzimy kontrwywiad dostarczył nam informacje o tym, jacy obcy agenci działają w kraju, którzy z nich są przekupni i za jaką cenę, a także, którzy agenci rozpracowali których. Liczba agentów ; są oni ponumerowani od do .

Zadanie

Ułóż program, który:

• wczytuje ze standardowego wejścia dane zgromadzone przez kontrwywiad,
• stwierdza, czy jest możliwe, by przez przekupienie odpowiednio wybranych agentów uzyskać informacje, uruchamiające łańcuch prowadzący do aresztowania wszystkich agentów w kraju i jeśli tak, oblicza minimalny koszt takiego zakupu, a jeśli nie, znajduje numer jednego z agentów, którego nie będzie można aresztować,
• zapisuje wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia jest zapisana jedna liczba naturalna . Jest to liczba wszystkich działających w kraju agentów, . W drugim wierszu jest zapisana jedna liczba naturalna . Jest to liczba wszystkich agentów przekupnych, . W kolejnych wierszach są zapisane informacje o przekupnych agentach. W każdym takim wierszu są zapisane dwie liczby całkowite dodatnie oddzielone odstępem — pierwsza z nich jest numerem przekupnego agenta, a druga to suma, za którą można go przekupić — jest to liczba nie większa niż .

Kolejny wiersz zawiera jedną liczbę , gdzie . Jest to liczba takich par , że agent rozpracował agenta . W następnych wierszach podane są wszystkie takie pary. W każdym z tych wierszy są zapisane dwie różne liczby ze zbioru oddzielone odstępem — pierwsza, to numer agenta, który rozpracował, a druga, to numer agenta, który został rozpracowany.

Wyjście

W pierwszym wierszu standardowego wyjścia należy zapisać jedno słowo: TAK — jeśli istnieje możliwość aresztowania wszystkich agentów działających w kraju, albo NIE — jeśli taka możliwość nie istnieje. W drugim wierszu należy zapisać jedną liczbę całkowitą dodatnią: minimalny koszt zakupu informacji wystarczających, by doprowadzić do aresztowania wszystkich agentów w kraju, albo numer dowolnego agenta, którego nie da się zaaresztować.

Przykład

Dla danych wejściowych:

3
2
1 10
2 100
2
1 3
2 3

poprawną odpowiedzią jest:

TAK
110

natomiast dla danych:

4
2
1 100
4 200
2
1 2
3 4

poprawnym wynikiem jest:

NIE
3

Autor zadania: Marcin Kubica.